#include "HashMap.h"
#include <iostream>

void MakeHeap(std::string &s, int n, int index)
{
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int max = index;
    if (left < n && s[left] > s[max])
    {
        max = left;
    }
    if (right < n && s[right] > s[max])
    {
        max = right;
    }
    if (max != index)
    {
        std::swap(s[index], s[max]);
        MakeHeap(s, n, max);
    }
}

void HeapSort(std::string &s)
{
    for (int i = s.size() / 2 - 1; i >= 0; i--)
    {
        MakeHeap(s, s.size(), i);
    }
    for (int i = s.size() - 1; i > 0; i--)
    {
        std::swap(s[0], s[i]);
        MakeHeap(s, i, 0);
    }
}

int main()
{
    // HashMap h(20);
    // h.Insert("zhangsan",20);
    // h.Insert("lisi",30);
    // h.Insert("wangwu",40);
    // h.Insert("zhaoliu",40);
    // h.Insert("zhouqi",23);
    // // h.show();
    // h.Remove("zhangsan");
    // h.show();

    // HashMap h(20);
    // h["zhangsan"] = 20;
    // h["lisi"] = 30;
    // h["wangwu"] = 40;
    // h.show();

    // std::cout<<h["lisi"]<<std::endl;

    // std::string s[6] = {"eat", "tea", "tan", "ate", "nat", "bat"};
    // HashMap m(10);
    // std::string tmp = "cabd";
    // HeapSort(tmp);
    // std::cout<<tmp<<std::endl;

    // for (int i = 0; i < 6; i++)
    // {
    //     std::string tmp = s[i];
    //     HeapSort(tmp);
    //     m.Insert(tmp, s[i]);
    //     //  m[tmp] = s[i];
    // }

    // m.showByGoup();

    int a[1000] = {0};
    for (int i = 0; i < 1000; i++)
    {
        a[i] = rand() % 10;
        std::cout << a[i] << " ";
    }
    std::cout << std::endl;

    HashMap m(100);
    // for (int i = 0; i < 10; i++)
    // {
    //     m.Insert(std::to_string(a[i]), 0);
    // }
    for (int i = 0; i < 1000; i++)
    {
        // m.Insert(std::to_string(a[i]), 0);
        m[std::to_string(a[i])]++;
    }

    m.show();
    
    // 三种
    // 1.快速排序
    // 2.超过递归深度 堆排序
    // 3.插入排序
    // std::sort();
    
    return 0;
}
